import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: ${USER}
 * Date: ${YEAR}-${MONTH}-${DAY}
 * Time: ${TIME}
 */
public class HashBuck {
    static class Node{  //哈希桶的每个元素是一个单链表
        public int key;
        public int val; //val这里我们默认全部设置999, 这次模拟不需要val
        public Node next;
        public Node(int key, int val){
            this.key = key;
            this.val = val;
        }
    }
    public static final double LOAD_FACTOR = 0.75;  //负载因子的上限
    public Node[] array;    //哈希数组
    public int usedSize;

    public HashBuck(){
        array = new Node[10];
    }

    public void push(int key, int val){
        int index = key % array.length; //除留余数法(哈希函数)找到哈希的位置
        //看一下key是不是在当前位置存储过，如果存储过更新最新的key(map的key不能有重复值)
        Node cur = array[index];
        while(cur != null){     //遍历单链表
            if(cur.key == key){
                cur.key = key;
                return;
            }
            cur = cur.next;
        }
        //走到这里说明是新元素
        //头插插入新元素
        Node node = new Node(key, val);
        node.next = array[index];
        array[index] = node;
        usedSize++;
        if(calaLoadFactor() >= LOAD_FACTOR){    //负载因子超过最大值
            resize();   //扩容
        }
    }

    private void resize() {
        Node[] newArray = new Node[2 * array.length];
        //重新哈希，遍历数组的每个链表, 因为之前数组长度是10, 2, 12都哈希到下标2， 现在20是数组长度，那么12该哈希到12下标了
        for(int i = 0; i < array.length; i++){
            Node cur = array[i];
            while(cur != null){
                int newIndex = cur.key % newArray.length; //新的哈希函数，重新定址
                Node curNext = cur.next;
                cur.next = newArray[newIndex];  //头插
                newArray[newIndex] = cur;
                cur = curNext;
            }
        }
        array = newArray;

    }

    private double calaLoadFactor() {
        return usedSize * 1.0 / array.length;   //计算负载因子(哈希数组元素个数 / 哈希数组长度)
    }
    public int get(int key){
        int index = key % array.length;
        Node cur = array[index];
        while(cur != null){
            if(cur.key == key){
                return cur.val;
            }
            cur = cur.next;
        }
        return -1;
      
    }
}